package net.sourceforge.wurfl.core.handlers.matchers.strategy.trie;

import java.util.Iterator;

import net.sourceforge.wurfl.core.handlers.matchers.strategy.trie.build.DataProvider;
import net.sourceforge.wurfl.core.handlers.matchers.strategy.trie.node.CharTrieNode;
import net.sourceforge.wurfl.core.handlers.matchers.strategy.trie.node.TrieNode;


/**
 * A (default) Trie implementation in which every node represents one character of a string
 * @author WURFL-PRO SRL, Rome, Italy
 */
public class CharTrie implements Trie {
	
	
	
	private CharTrieNode root;

	public CharTrie() {
		this.root = new CharTrieNode(new Character('_'));
	}
	
	public CharTrie(DataProvider dataProvider) {
		this.root = new CharTrieNode(new Character('_')); 
		for (Iterator dataIterator = dataProvider.getData().iterator(); dataIterator.hasNext();) {
			this.insert(dataIterator.next().toString(),0,this.getRoot());
		}
	}
	
	public void setRoot(CharTrieNode root) {
		this.root = root;
	}


	public TrieNode getRoot() {
		return root;
	}



	/**
	 * put an Object into the Trie 
	 */
	public void put(Object object) {
		this.insert(object.toString(), 0, this.getRoot());
	}

	/** recursive sliding window put method */
	private void insert(String data, int index, TrieNode trieNode) {
		if (data != null && data.length()>index) {
			Character toInsert = new Character(data.charAt(index));
			CharTrieNode selectedNode = (CharTrieNode) trieNode.getSubTrie().get(toInsert);
			
			if (selectedNode == null) {
				selectedNode = new CharTrieNode(toInsert);
				trieNode.getSubTrie().put(toInsert, selectedNode);
			} 
			index++;
			insert(data, index, selectedNode);
		} else {
			trieNode.setValue(data);
		}
	}
	
	
	/** 
	 * search for an Object with the specified String key
	 */
	public Object search(String key) {
		String keyString = key.toString();
		return get(root, keyString, 0);
	}
	
	/** 
	 * recursive searching method
	 * @param root
	 * @param keyString
	 * @param index
	 * @return
	 */
	private Object get(CharTrieNode root, String keyString, int index) {
		if (root == null) {
			return null;
		}
		if (index == keyString.length()) {
			return root.getValue();
		}
		Character c = new Character(keyString.charAt(index));
		return get((CharTrieNode) root.getSubTrie().get(c), keyString, index + 1);
	}

	public Object search(String key, Integer tolerance) {
		// TODO Auto-generated method stub
		return null;
	}

}
